Educational Codeforces Round 46 (Rated for Div. 2)

C一眼看过去不会啊,然后就跑路了,咕咕咕

突然发现教育场是ICPC赛制,如梦初醒啊


B.Light It Up

题意

有一盏灯,$0$时刻是开着的,给你一个时间序列,依次为关,开,关….的时间,现在你可以插入一个时间,插入在开后面则为关,后面的则会变成相反的,反之同理,问最大开灯的时间

题解

不难发现,插在任意一个区间里,它后面的区间开关时间正好反过来了,故前缀和分别预处理好每个位置之前的开关灯的时间,枚举位置去 $max$ 即可


C.Covered Points Count

题意

给n条线段,问别覆盖次数分别为1~n次数的点分别为多少个$(n<2e5,len < 10^{18})$

题解

我怎么这么2啊,这题不会???

一眼想到的是假如 $10^{7}$ 怎么做?
显然直接对 $l,r+1$ 分别打上 $1,-1$ 的标记前缀和过去就行了啊,但这个区间长度更大,前缀和肯定不行,但当时我怎么这么蠢啊,类比这种思想,直接把所有点存起来,遇到区间左端点说明覆盖的边多了一条,遇到右端点说明覆盖的区间少了一条,直接递推过去即可

黑科技


D.Yet Another Problem On a Subsequence

题意

给你 $n$ 个数字 $(n <= 1000)$, 问你有多少个子序列是 $good sequence$, $good sequence$ 的定义是能变成若干个 $good arrays$,$good array$ 的定义是这个数组的第一个元素的值等于这个数组的 $length-1$

题解

分析可知,每个$good sequence$可以由自己当前这个$good array$组成,也可以和它所在$good array$后面的$good array$组成
定义:$dp[i]$ : 以 $i$ 为起点的所有 $good sequence$ 且位置 $i$的$good array$必须取(前提当然是:$a[i]$这个位置满足$good array$)
转移:首先位置$i$本身$good array$,然后考虑有多个$good array$,组合数$*dp[j]$即可


E. We Need More Bosses

题意

一条路径上必经的边为关键边,现在让你找一条路径,使得其关键边最多,输出最多的数量

题解


F. One Occurrence

题意

给一个序列,q次查询,每次查询区间[L,R]内只出现一次的数字,输出任意一个,如果没有就输出0

题解